In your final repo, there should be an R markdown file that organizes all computational steps for evaluating your proposed Facial Expression Recognition framework.

This file is currently a template for running evaluation experiments. You should update it according to your codes but following precisely the same structure.

if(!require("EBImage")){
  source("https://bioconductor.org/biocLite.R")
  biocLite("EBImage")
}
Loading required package: EBImage
if(!require("R.matlab")){
  install.packages("R.matlab")
}
Loading required package: R.matlab
R.matlab v3.6.2 (2018-09-26) successfully loaded. See ?R.matlab for help.

Attaching package: ‘R.matlab’

The following objects are masked from ‘package:base’:

    getOption, isOpen
if(!require("readxl")){
  install.packages("readxl")
}
Loading required package: readxl
if(!require("dplyr")){
  install.packages("dplyr")
}
Loading required package: dplyr

Attaching package: ‘dplyr’

The following object is masked from ‘package:EBImage’:

    combine

The following objects are masked from ‘package:stats’:

    filter, lag

The following objects are masked from ‘package:base’:

    intersect, setdiff, setequal, union
if(!require("readxl")){
  install.packages("readxl")
}
if(!require("ggplot2")){
  install.packages("ggplot2")
}
Loading required package: ggplot2
RStudio Community is a great place to get help:
https://community.rstudio.com/c/tidyverse.
if(!require("caret")){
  install.packages("caret")
}
Loading required package: caret
Loading required package: lattice
library(R.matlab)
library(readxl)
library(dplyr)
library(EBImage)
library(ggplot2)
library(caret)

Step 0 set work directories, extract paths, summarize

set.seed(0)
setwd("~/Google Drive (yw3285@columbia.edu)/RA/FER/Project3-FacialEmotionRecognition/doc")
# here replace it with your own path or manually set it in RStudio to where this rmd file is located. 
# use relative path for reproducibility

Training images are located in data/train_images folder. The file names are in the format of XX_XXX_XXXX; the first 2 digits represent emotion index, the following 3 digits represent identity(person) index, and the last four digits can be ignored. In current step, we extract paths to images and fiducial points, and corresponding emotion indices and identity indices.

#form paths of training images
image.path <- paste("../data/train_images", 
      list.files("../data/train_images"),
     sep="/")
#form paths of fiducial points corresponding to training images
tmp <- gsub(image.path, pattern = 'jpg', replacement = 'mat')
point.path <- gsub(tmp, pattern = 'images', replacement = 'points')
#extract emotion index from paths
emotion_idx <- substr(image.path, 22, 23)
emotion_idx <- as.numeric(ifelse(as.numeric(emotion_idx < 10), substr(emotion_idx, 2, 2), emotion_idx))
identity <- as.numeric(substr(image.path, 25, 27))
emotion_table <- read_xls("../data/AU_annotation_all_subjects.xls")

-
/
                                                                                               
info <- data.frame(stringsAsFactors = F, image.path = image.path, point.path = point.path, identity = identity, emotion_idx = emotion_idx) %>% inner_join(emotion_table, by = c('emotion_idx' = 'idx')) %>%  mutate(Index = 1:length(image.path))
head(info)

Step 1: set up controls for evaluation experiments.

In this chunk, we have a set of controls for the evaluation experiments.

run.cv=TRUE # run cross-validation on the training set
K <- 5  # number of CV folds
run.feature.train=TRUE # process features for training set
run.test=TRUE # run evaluation on an independent test set
run.feature.test=TRUE # process features for test set

Using cross-validation or independent test set evaluation, we compare the performance of models with different specifications. In this Starter Code, we tune parameter k (number of neighbours) for KNN.

k = c(5,10,50,100,150,200)
model_labels = paste("KNN with K =", k)

Step 2: import data and train-test split

#train-test split
n <- nrow(info)
n_train <- round(n*(4/5), 0)
train_idx <- sample(info$Index, n_train, replace = F)
test_idx <- setdiff(info$Index,train_idx)

If you choose to use extract features from images, such as using Gabor filter, R memory will exhaust all images are read together. The solution is to repeat reading a smaller batch and process them.

EBImage::readImage(image.path)
Error: vector memory exhausted (limit reached?)

Fiducial points are stored in matlab format. In this step, we read them and store them in a list.

readMat.matrix <- function(path){
     #print(path)
     return(round(readMat(path)[[1]],0))
}

#load fiducial points
fiducial_pt_list <- lapply(point.path, readMat.matrix)

Step 3: construct features and responses

feature.R should be the wrapper for all your feature engineering functions and options. The function feature( ) should have options that correspond to different scenarios for your project and produces an R object that contains features and responses that are required by all the models you are going to evaluate later.

fiducial_pt_list <- lapply(point.path, readMat.matrix)
source("../lib/feature.R")
tm_feature_train <- NA
if(run.feature.train){
  tm_feature_train <- system.time(dat_train <- feature(fiducial_pt_list, train_idx))
}
tm_feature_test <- NA
if(run.feature.train){
  tm_feature_test <- system.time(dat_test <- feature(fiducial_pt_list, test_idx))
}
save(dat_train, file="../output/feature_train.RData")
save(dat_test, file="../output/feature_test.RData")

Step 4: Train a classification model with training features and responses

Call the train model and test model from library.

train.R and test.R should be wrappers for all your model training steps and your classification/prediction steps.

source("../lib/train_knn.R")
source("../lib/test_knn.R")

Model selection with cross-validation

  • Do model selection by choosing among different values of training model parameters.
source("../lib/cross_validation_knn.R")
if(run.cv){
  err_cv <- matrix(0, nrow = length(k), ncol = 2)
  for(i in 1:length(k)){
    cat("k=", k[i], "\n")
    err_cv[i,] <- cv.function(dat_train, K, k[i])
  save(err_cv, file="../output/err_cv.RData")
  }
}

Visualize cross-validation results.

if(run.cv){
  load("../output/err_cv.RData")
  err_cv <- as.data.frame(err_cv) 
  colnames(err_cv) <- c("mean_error", "sd_error")
  err_cv$k = as.factor(k)
  err_cv %>% 
    ggplot(aes(x = k, y = mean_error,
               ymin = mean_error - sd_error, ymax = mean_error + sd_error)) + 
    geom_crossbar() +
    theme(axis.text.x = element_text(angle = 90, hjust = 1))
}

  • Choose the “best” parameter value
if(run.cv){
  model_best <- k[which.min(err_cv[,1])]
}
par_best <- list(k = model_best)
  • Train the model with the entire training set using the selected model (model parameter) via cross-validation.
#tm_train=NA
#tm_train <- system.time(fit_train <- train(dat_train, par_best))
#save(fit_train, file="../output/fit_train.RData")

Step 5: Run test on test images

tm_test=NA
if(run.test){
  load(file="../output/fit_train.RData")
  tm_test <- system.time(pred <- test(model_best, dat_test))
}
accu <- mean(dat_test$emotion_idx == pred)
cat("The accuracy of model:", model_labels[which.min(err_cv[,1])], "is", accu, ".\n")
The accuracy of model: KNN with K = 21 is 0.242 .
library(caret)
confusionMatrix(pred, dat_test$emotion_idx)
Confusion Matrix and Statistics

          Reference
Prediction  1  2  3  5  6  7  8  9 10 11 12 13 14 15 16 18 21 22 23 24 25 26
        1   9  0  4  2  2  2  1  1  1  5  1  1  0  0  2  4  3  2  1  0  1  2
        2   1 17  0  0  0  0  0  0  7  0  0  0  0  0  0  1  0  0  0  1  0  1
        3   1  0 11  0  0  2  0  0  1  4  0  0  1  0  0  3  1  0  0  0  0  1
        5   1  0  1  8  0  0  1  0  0  3  3  1  5  0  1  0  0  0  0  0  2  0
        6   0  0  0  0  7  0  1  0  0  0  0  0  0  1  1  0  1  2  0  0  0  0
        7   1  0  0  1  0  7  1  0  2  1  2  2  1  0  0  1  0  0  0  0  0  0
        8   4  1  1  0  2  0  3  2  1  1  0  0  0  7  1  0  1  1  3  1  5  0
        9   0  1  0  0  1  0  1 15  1  0  0  0  0  0  0  0  0  0  0  1  1  0
        10  0  2  0  0  0  0  1  2  5  0  1  0  0  0  0  1  0  0  1  1  0  0
        11  1  0  3  7  0  1  0  1  0  2  1  1  3  0  0  0  0  0  2  0  1  1
        12  0  1  1  3  0  2  0  0  0  1  4  1  2  1  0  1  0  0  1  1  1  1
        13  0  2  1  4  0  3  0  0  1  0  5  2  3  0  0  0  1  0  0  0  2  3
        14  1  0  3  3  0  0  0  0  0  3  3  3  2  1  2  0  1  0  0  1  2  4
        15  0  0  0  1  3  0  4  0  0  0  0  1  0  9  5  0  2  1  4  2  4  1
        16  0  0  1  0  4  0  0  2  0  0  0  1  0  4  3  0  2  2  0  3  5  1
        18  1  0  0  0  1  2  2  0  0  0  0  1  0  0  3  5  0  1  0  1  0  0
        21  0  0  0  0  2  0  2  2  0  0  0  1  0  1  0  1  3  1  1  3  0  0
        22  0  0  2  0  0  0  3  1  0  0  0  0  0  0  3  1  3  5  2  1  0  2
        23  0  0  0  1  2  0  5  0  0  0  1  0  0  1  1  2  1  2  1  2  1  1
        24  0  0  1  0  0  1  1  0  0  0  0  0  0  0  0  0  2  0  1  2  1  0
        25  0  0  0  0  0  1  0  0  2  0  0  1  0  1  0  0  0  0  1  1  0  0
        26  0  1  1  0  0  0  1  0  2  2  0  1  2  0  1  0  1  0  0  2  1  1

Overall Statistics
                                         
               Accuracy : 0.242          
                 95% CI : (0.2051, 0.282)
    No Information Rate : 0.06           
    P-Value [Acc > NIR] : < 2.2e-16      
                                         
                  Kappa : 0.2059         
                                         
 Mcnemar's Test P-Value : NA             

Statistics by Class:

                     Class: 1 Class: 2 Class: 3 Class: 5 Class: 6 Class: 7 Class: 8 Class: 9
Sensitivity            0.4500   0.6800   0.3667   0.2667   0.2917   0.3333  0.11111   0.5769
Specificity            0.9271   0.9768   0.9702   0.9617   0.9874   0.9749  0.93446   0.9873
Pos Pred Value         0.2045   0.6071   0.4400   0.3077   0.5385   0.3684  0.08824   0.7143
Neg Pred Value         0.9759   0.9831   0.9600   0.9536   0.9651   0.9709  0.94850   0.9770
Prevalence             0.0400   0.0500   0.0600   0.0600   0.0480   0.0420  0.05400   0.0520
Detection Rate         0.0180   0.0340   0.0220   0.0160   0.0140   0.0140  0.00600   0.0300
Detection Prevalence   0.0880   0.0560   0.0500   0.0520   0.0260   0.0380  0.06800   0.0420
Balanced Accuracy      0.6885   0.8284   0.6684   0.6142   0.6395   0.6541  0.52279   0.7821
                     Class: 10 Class: 11 Class: 12 Class: 13 Class: 14 Class: 15 Class: 16
Sensitivity             0.2174   0.09091    0.1905   0.11765   0.10526    0.3462    0.1304
Specificity             0.9811   0.95397    0.9645   0.94824   0.94387    0.9409    0.9476
Pos Pred Value          0.3571   0.08333    0.1905   0.07407   0.06897    0.2432    0.1071
Neg Pred Value          0.9630   0.95798    0.9645   0.96829   0.96391    0.9633    0.9576
Prevalence              0.0460   0.04400    0.0420   0.03400   0.03800    0.0520    0.0460
Detection Rate          0.0100   0.00400    0.0080   0.00400   0.00400    0.0180    0.0060
Detection Prevalence    0.0280   0.04800    0.0420   0.05400   0.05800    0.0740    0.0560
Balanced Accuracy       0.5993   0.52244    0.5775   0.53294   0.52457    0.6435    0.5390
                     Class: 18 Class: 21 Class: 22 Class: 23 Class: 24 Class: 25 Class: 26
Sensitivity             0.2500    0.1364    0.2941   0.05556   0.08696    0.0000   0.05263
Specificity             0.9750    0.9707    0.9627   0.95851   0.98532    0.9852   0.96881
Pos Pred Value          0.2941    0.1765    0.2174   0.04762   0.22222    0.0000   0.06250
Neg Pred Value          0.9689    0.9607    0.9748   0.96451   0.95723    0.9452   0.96281
Prevalence              0.0400    0.0440    0.0340   0.03600   0.04600    0.0540   0.03800
Detection Rate          0.0100    0.0060    0.0100   0.00200   0.00400    0.0000   0.00200
Detection Prevalence    0.0340    0.0340    0.0460   0.04200   0.01800    0.0140   0.03200
Balanced Accuracy       0.6125    0.5535    0.6284   0.50703   0.53614    0.4926   0.51072

Note that the accuracy is not high but is better than that of ramdom guess(4.5%).

Summarize Running Time

Prediction performance matters, so does the running times for constructing features and for training the model, especially when the computation resource is limited.

cat("Time for constructing training features=", tm_feature_train[1], "s \n")
Time for constructing training features= 1.753 s 
cat("Time for constructing testing features=", tm_feature_test[1], "s \n")
Time for constructing testing features= 0.185 s 
#cat("Time for training model=", tm_train[1], "s \n")
cat("Time for testing model=", tm_test[1], "s \n")
Time for testing model= 57.639 s 

Reference

LS0tCnRpdGxlOiAiTWFpbiIKYXV0aG9yOiAiQ2hlbmdsaWFuZyBUYW5nLCBZdWppZSBXYW5nLCBUaWFuIFpoZW5nIgpvdXRwdXQ6CiAgaHRtbF9kb2N1bWVudDoKICAgIGRmX3ByaW50OiBwYWdlZAotLS0KSW4geW91ciBmaW5hbCByZXBvLCB0aGVyZSBzaG91bGQgYmUgYW4gUiBtYXJrZG93biBmaWxlIHRoYXQgb3JnYW5pemVzICoqYWxsIGNvbXB1dGF0aW9uYWwgc3RlcHMqKiBmb3IgZXZhbHVhdGluZyB5b3VyIHByb3Bvc2VkIEZhY2lhbCBFeHByZXNzaW9uIFJlY29nbml0aW9uIGZyYW1ld29yay4gCgpUaGlzIGZpbGUgaXMgY3VycmVudGx5IGEgdGVtcGxhdGUgZm9yIHJ1bm5pbmcgZXZhbHVhdGlvbiBleHBlcmltZW50cy4gWW91IHNob3VsZCB1cGRhdGUgaXQgYWNjb3JkaW5nIHRvIHlvdXIgY29kZXMgYnV0IGZvbGxvd2luZyBwcmVjaXNlbHkgdGhlIHNhbWUgc3RydWN0dXJlLiAKCmBgYHtyIG1lc3NhZ2U9RkFMU0V9CmlmKCFyZXF1aXJlKCJFQkltYWdlIikpewogIHNvdXJjZSgiaHR0cHM6Ly9iaW9jb25kdWN0b3Iub3JnL2Jpb2NMaXRlLlIiKQogIGJpb2NMaXRlKCJFQkltYWdlIikKfQppZighcmVxdWlyZSgiUi5tYXRsYWIiKSl7CiAgaW5zdGFsbC5wYWNrYWdlcygiUi5tYXRsYWIiKQp9CmlmKCFyZXF1aXJlKCJyZWFkeGwiKSl7CiAgaW5zdGFsbC5wYWNrYWdlcygicmVhZHhsIikKfQoKaWYoIXJlcXVpcmUoImRwbHlyIikpewogIGluc3RhbGwucGFja2FnZXMoImRwbHlyIikKfQppZighcmVxdWlyZSgicmVhZHhsIikpewogIGluc3RhbGwucGFja2FnZXMoInJlYWR4bCIpCn0KCmlmKCFyZXF1aXJlKCJnZ3Bsb3QyIikpewogIGluc3RhbGwucGFja2FnZXMoImdncGxvdDIiKQp9CgppZighcmVxdWlyZSgiY2FyZXQiKSl7CiAgaW5zdGFsbC5wYWNrYWdlcygiY2FyZXQiKQp9CgpsaWJyYXJ5KFIubWF0bGFiKQpsaWJyYXJ5KHJlYWR4bCkKbGlicmFyeShkcGx5cikKbGlicmFyeShFQkltYWdlKQpsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkoY2FyZXQpCmBgYAoKIyMjIFN0ZXAgMCBzZXQgd29yayBkaXJlY3RvcmllcywgZXh0cmFjdCBwYXRocywgc3VtbWFyaXplCmBgYHtyIHdrZGlyLCBldmFsPUZBTFNFfQpzZXQuc2VlZCgwKQpzZXR3ZCgifi9Hb29nbGUgRHJpdmUgKHl3MzI4NUBjb2x1bWJpYS5lZHUpL1JBL0ZFUi9Qcm9qZWN0My1GYWNpYWxFbW90aW9uUmVjb2duaXRpb24vZG9jIikKIyBoZXJlIHJlcGxhY2UgaXQgd2l0aCB5b3VyIG93biBwYXRoIG9yIG1hbnVhbGx5IHNldCBpdCBpbiBSU3R1ZGlvIHRvIHdoZXJlIHRoaXMgcm1kIGZpbGUgaXMgbG9jYXRlZC4gCiMgdXNlIHJlbGF0aXZlIHBhdGggZm9yIHJlcHJvZHVjaWJpbGl0eQpgYGAKClRyYWluaW5nIGltYWdlcyBhcmUgbG9jYXRlZCBpbiBkYXRhL3RyYWluX2ltYWdlcyBmb2xkZXIuIFRoZSBmaWxlIG5hbWVzIGFyZSBpbiB0aGUgZm9ybWF0IG9mIFhYX1hYWF9YWFhYOyB0aGUgZmlyc3QgMiBkaWdpdHMgcmVwcmVzZW50IGVtb3Rpb24gaW5kZXgsIHRoZSBmb2xsb3dpbmcgMyBkaWdpdHMgcmVwcmVzZW50IGlkZW50aXR5KHBlcnNvbikgaW5kZXgsIGFuZCB0aGUgbGFzdCBmb3VyIGRpZ2l0cyBjYW4gYmUgaWdub3JlZC4gSW4gY3VycmVudCBzdGVwLCB3ZSBleHRyYWN0IHBhdGhzIHRvIGltYWdlcyBhbmQgZmlkdWNpYWwgcG9pbnRzLCBhbmQgY29ycmVzcG9uZGluZyBlbW90aW9uIGluZGljZXMgYW5kIGlkZW50aXR5IGluZGljZXMuIAoKYGBge3J9CiNmb3JtIHBhdGhzIG9mIHRyYWluaW5nIGltYWdlcwppbWFnZS5wYXRoIDwtIHBhc3RlKCIuLi9kYXRhL3RyYWluX2ltYWdlcyIsIAogICAgICBsaXN0LmZpbGVzKCIuLi9kYXRhL3RyYWluX2ltYWdlcyIpLAogICAgIHNlcD0iLyIpCgojZm9ybSBwYXRocyBvZiBmaWR1Y2lhbCBwb2ludHMgY29ycmVzcG9uZGluZyB0byB0cmFpbmluZyBpbWFnZXMKdG1wIDwtIGdzdWIoaW1hZ2UucGF0aCwgcGF0dGVybiA9ICdqcGcnLCByZXBsYWNlbWVudCA9ICdtYXQnKQpwb2ludC5wYXRoIDwtIGdzdWIodG1wLCBwYXR0ZXJuID0gJ2ltYWdlcycsIHJlcGxhY2VtZW50ID0gJ3BvaW50cycpCgoKI2V4dHJhY3QgZW1vdGlvbiBpbmRleCBmcm9tIHBhdGhzCmVtb3Rpb25faWR4IDwtIHN1YnN0cihpbWFnZS5wYXRoLCAyMiwgMjMpCmVtb3Rpb25faWR4IDwtIGFzLm51bWVyaWMoaWZlbHNlKGFzLm51bWVyaWMoZW1vdGlvbl9pZHggPCAxMCksIHN1YnN0cihlbW90aW9uX2lkeCwgMiwgMiksIGVtb3Rpb25faWR4KSkKCmlkZW50aXR5IDwtIGFzLm51bWVyaWMoc3Vic3RyKGltYWdlLnBhdGgsIDI1LCAyNykpCmVtb3Rpb25fdGFibGUgPC0gcmVhZF94bHMoIi4uL2RhdGEvQVVfYW5ub3RhdGlvbl9hbGxfc3ViamVjdHMueGxzIikKCmluZm8gPC0gZGF0YS5mcmFtZShzdHJpbmdzQXNGYWN0b3JzID0gRiwgaW1hZ2UucGF0aCA9IGltYWdlLnBhdGgsIHBvaW50LnBhdGggPSBwb2ludC5wYXRoLCBpZGVudGl0eSA9IGlkZW50aXR5LCBlbW90aW9uX2lkeCA9IGVtb3Rpb25faWR4KSAlPiUgaW5uZXJfam9pbihlbW90aW9uX3RhYmxlLCBieSA9IGMoJ2Vtb3Rpb25faWR4JyA9ICdpZHgnKSkgJT4lICBtdXRhdGUoSW5kZXggPSAxOmxlbmd0aChpbWFnZS5wYXRoKSkKCmhlYWQoaW5mbykKYGBgCgoKCgojIyMgU3RlcCAxOiBzZXQgdXAgY29udHJvbHMgZm9yIGV2YWx1YXRpb24gZXhwZXJpbWVudHMuCgpJbiB0aGlzIGNodW5rLCB3ZSBoYXZlIGEgc2V0IG9mIGNvbnRyb2xzIGZvciB0aGUgZXZhbHVhdGlvbiBleHBlcmltZW50cy4gCgorIChUL0YpIGNyb3NzLXZhbGlkYXRpb24gb24gdGhlIHRyYWluaW5nIHNldAorIChudW1iZXIpIEssIHRoZSBudW1iZXIgb2YgQ1YgZm9sZHMKKyAoVC9GKSBwcm9jZXNzIGZlYXR1cmVzIGZvciB0cmFpbmluZyBzZXQKKyAoVC9GKSBydW4gZXZhbHVhdGlvbiBvbiBhbiBpbmRlcGVuZGVudCB0ZXN0IHNldAorIChUL0YpIHByb2Nlc3MgZmVhdHVyZXMgZm9yIHRlc3Qgc2V0CgpgYGB7ciBleHBfc2V0dXB9CnJ1bi5jdj1UUlVFICMgcnVuIGNyb3NzLXZhbGlkYXRpb24gb24gdGhlIHRyYWluaW5nIHNldApLIDwtIDUgICMgbnVtYmVyIG9mIENWIGZvbGRzCnJ1bi5mZWF0dXJlLnRyYWluPVRSVUUgIyBwcm9jZXNzIGZlYXR1cmVzIGZvciB0cmFpbmluZyBzZXQKcnVuLnRlc3Q9VFJVRSAjIHJ1biBldmFsdWF0aW9uIG9uIGFuIGluZGVwZW5kZW50IHRlc3Qgc2V0CnJ1bi5mZWF0dXJlLnRlc3Q9VFJVRSAjIHByb2Nlc3MgZmVhdHVyZXMgZm9yIHRlc3Qgc2V0CmBgYApVc2luZyBjcm9zcy12YWxpZGF0aW9uIG9yIGluZGVwZW5kZW50IHRlc3Qgc2V0IGV2YWx1YXRpb24sIHdlIGNvbXBhcmUgdGhlIHBlcmZvcm1hbmNlIG9mIG1vZGVscyB3aXRoIGRpZmZlcmVudCBzcGVjaWZpY2F0aW9ucy4gSW4gdGhpcyBTdGFydGVyIENvZGUsIHdlIHR1bmUgcGFyYW1ldGVyIGsgKG51bWJlciBvZiBuZWlnaGJvdXJzKSBmb3IgS05OLgoKYGBge3IgbW9kZWxfc2V0dXB9CmsgPSBjKDUsMTEsMjEsMzEsNDEsNTEpCm1vZGVsX2xhYmVscyA9IHBhc3RlKCJLTk4gd2l0aCBLID0iLCBrKQpgYGAKCiMjIyBTdGVwIDI6IGltcG9ydCBkYXRhIGFuZCB0cmFpbi10ZXN0IHNwbGl0IApgYGB7cn0KI3RyYWluLXRlc3Qgc3BsaXQKbiA8LSBucm93KGluZm8pCm5fdHJhaW4gPC0gcm91bmQobiooNC81KSwgMCkKdHJhaW5faWR4IDwtIHNhbXBsZShpbmZvJEluZGV4LCBuX3RyYWluLCByZXBsYWNlID0gRikKdGVzdF9pZHggPC0gc2V0ZGlmZihpbmZvJEluZGV4LHRyYWluX2lkeCkKYGBgCgpJZiB5b3UgY2hvb3NlIHRvIHVzZSBleHRyYWN0IGZlYXR1cmVzIGZyb20gaW1hZ2VzLCBzdWNoIGFzIHVzaW5nIEdhYm9yIGZpbHRlciwgUiBtZW1vcnkgd2lsbCBleGhhdXN0IGFsbCBpbWFnZXMgYXJlIHJlYWQgdG9nZXRoZXIuIFRoZSBzb2x1dGlvbiBpcyB0byByZXBlYXQgcmVhZGluZyBhIHNtYWxsZXIgYmF0Y2ggYW5kIHByb2Nlc3MgdGhlbS4gCmBgYHtyfQpFQkltYWdlOjpyZWFkSW1hZ2UoaW1hZ2UucGF0aFsxXSkKYGBgCgpGaWR1Y2lhbCBwb2ludHMgYXJlIHN0b3JlZCBpbiBtYXRsYWIgZm9ybWF0LiBJbiB0aGlzIHN0ZXAsIHdlIHJlYWQgdGhlbSBhbmQgc3RvcmUgdGhlbSBpbiBhIGxpc3QuCmBgYHtyIHJlYWQgZmlkdWNpYWwgcG9pbnRzfQpyZWFkTWF0Lm1hdHJpeCA8LSBmdW5jdGlvbihwYXRoKXsKICAgICAjcHJpbnQocGF0aCkKICAgICByZXR1cm4ocm91bmQocmVhZE1hdChwYXRoKVtbMV1dLDApKQp9CgojbG9hZCBmaWR1Y2lhbCBwb2ludHMKZmlkdWNpYWxfcHRfbGlzdCA8LSBsYXBwbHkocG9pbnQucGF0aCwgcmVhZE1hdC5tYXRyaXgpCmBgYAoKIyMjIFN0ZXAgMzogY29uc3RydWN0IGZlYXR1cmVzIGFuZCByZXNwb25zZXMKCisgVGhlIGZvbGxvdyBwbG90cyBzaG93IGhvdyBwYWlyd2lzZSBkaXN0YW5jZSBiZXR3ZWVuIGZpZHVjaWFsIHBvaW50cyBjYW4gd29yayBhcyBmZWF0dXJlIGZvciBmYWNpYWwgZW1vdGlvbiByZWNvZ25pdGlvbi4KCiAgKyBJbiB0aGUgZmlyc3QgY29sdW1uLCA3OCBmaWR1Y2lhbHMgcG9pbnRzIG9mIGVhY2ggZW1vdGlvbiBhcmUgbWFya2VkIGluIG9yZGVyLiAKICArIEluIHRoZSBzZWNvbmQgY29sdW1uIGRpc3RyaWJ1dGlvbnMgb2YgdmVydGljYWwgZGlzdGFuY2UgYmV0d2VlbiByaWdodCBwdXBpbCgxKSBhbmQgIHJpZ2h0IGJyb3cgcGVhaygyMSkgYXJlIHNob3duIGluICBoaXN0b2dyYW1zLiBGb3IgZXhhbXBsZSwgdGhlIGRpc3RhbmNlIG9mIGFuIGFuZ3J5IGZhY2UgdGVuZHMgdG8gYmUgc2hvcnRlciB0aGFuIHRoYXQgb2YgYSBzdXJwcmlzZWQgZmFjZS4KICArIFRoZSB0aGlyZCBjb2x1bW4gaXMgdGhlIGRpc3RyaWJ1dGlvbnMgb2YgdmVydGljYWwgZGlzdGFuY2VzIGJldHdlZW4gcmlnaHQgbW91dGggY29ybmVyKDUwKQphbmQgdGhlIG1pZHBvaW50IG9mIHRoZSB1cHBlciBsaXAoNTIpLiAgRm9yIGV4YW1wbGUsIHRoZSBkaXN0YW5jZSBvZiBhbiBoYXBweSBmYWNlIHRlbmRzIHRvIGJlIHNob3J0ZXIgdGhhbiB0aGF0IG9mIGEgc2FkIGZhY2UuCgohW10oLi4vZmlncy9lbW90aW9uX2hpc3QuanBnKQoKYGZlYXR1cmUuUmAgc2hvdWxkIGJlIHRoZSB3cmFwcGVyIGZvciBhbGwgeW91ciBmZWF0dXJlIGVuZ2luZWVyaW5nIGZ1bmN0aW9ucyBhbmQgb3B0aW9ucy4gVGhlIGZ1bmN0aW9uIGBmZWF0dXJlKCApYCBzaG91bGQgaGF2ZSBvcHRpb25zIHRoYXQgY29ycmVzcG9uZCB0byBkaWZmZXJlbnQgc2NlbmFyaW9zIGZvciB5b3VyIHByb2plY3QgYW5kIHByb2R1Y2VzIGFuIFIgb2JqZWN0IHRoYXQgY29udGFpbnMgZmVhdHVyZXMgYW5kIHJlc3BvbnNlcyB0aGF0IGFyZSByZXF1aXJlZCBieSBhbGwgdGhlIG1vZGVscyB5b3UgYXJlIGdvaW5nIHRvIGV2YWx1YXRlIGxhdGVyLiAKICAKICArIGBmZWF0dXJlLlJgCiAgKyBJbnB1dDogbGlzdCBvZiBpbWFnZXMgb3IgZmlkdWNpYWwgcG9pbnQKICArIE91dHB1dDogYW4gUkRhdGEgZmlsZSB0aGF0IGNvbnRhaW5zIGV4dHJhY3RlZCBmZWF0dXJlcyBhbmQgY29ycmVzcG9uZGluZyByZXNwb25zZXMKCmBgYHtyIGZlYXR1cmV9CmZpZHVjaWFsX3B0X2xpc3QgPC0gbGFwcGx5KHBvaW50LnBhdGgsIHJlYWRNYXQubWF0cml4KQpzb3VyY2UoIi4uL2xpYi9mZWF0dXJlLlIiKQp0bV9mZWF0dXJlX3RyYWluIDwtIE5BCmlmKHJ1bi5mZWF0dXJlLnRyYWluKXsKICB0bV9mZWF0dXJlX3RyYWluIDwtIHN5c3RlbS50aW1lKGRhdF90cmFpbiA8LSBmZWF0dXJlKGZpZHVjaWFsX3B0X2xpc3QsIHRyYWluX2lkeCkpCn0KCnRtX2ZlYXR1cmVfdGVzdCA8LSBOQQppZihydW4uZmVhdHVyZS50cmFpbil7CiAgdG1fZmVhdHVyZV90ZXN0IDwtIHN5c3RlbS50aW1lKGRhdF90ZXN0IDwtIGZlYXR1cmUoZmlkdWNpYWxfcHRfbGlzdCwgdGVzdF9pZHgpKQp9CgpzYXZlKGRhdF90cmFpbiwgZmlsZT0iLi4vb3V0cHV0L2ZlYXR1cmVfdHJhaW4uUkRhdGEiKQpzYXZlKGRhdF90ZXN0LCBmaWxlPSIuLi9vdXRwdXQvZmVhdHVyZV90ZXN0LlJEYXRhIikKYGBgCgojIyMgU3RlcCA0OiBUcmFpbiBhIGNsYXNzaWZpY2F0aW9uIG1vZGVsIHdpdGggdHJhaW5pbmcgZmVhdHVyZXMgYW5kIHJlc3BvbnNlcwpDYWxsIHRoZSB0cmFpbiBtb2RlbCBhbmQgdGVzdCBtb2RlbCBmcm9tIGxpYnJhcnkuIAoKYHRyYWluLlJgIGFuZCBgdGVzdC5SYCBzaG91bGQgYmUgd3JhcHBlcnMgZm9yIGFsbCB5b3VyIG1vZGVsIHRyYWluaW5nIHN0ZXBzIGFuZCB5b3VyIGNsYXNzaWZpY2F0aW9uL3ByZWRpY3Rpb24gc3RlcHMuIAoKKyBgdHJhaW4uUmAKICArIElucHV0OiBhIGRhdGEgZnJhbWUgY29udGFpbmluZyBmZWF0dXJlcyBhbmQgbGFiZWxzIGFuZCBhIHBhcmFtZXRlciBsaXN0LgogICsgT3V0cHV0OmEgdHJhaW5lZCBtb2RlbAorIGB0ZXN0LlJgCiAgKyBJbnB1dDogdGhlIGZpdHRlZCBjbGFzc2lmaWNhdGlvbiBtb2RlbCB1c2luZyB0cmFpbmluZyBkYXRhIGFuZCBwcm9jZXNzZWQgZmVhdHVyZXMgZnJvbSB0ZXN0aW5nIGltYWdlcyAKICArIElucHV0OiBhbiBSIG9iamVjdCB0aGF0IGNvbnRhaW5zIGEgdHJhaW5lZCBjbGFzc2lmaWVyLgogICsgT3V0cHV0OiB0cmFpbmluZyBtb2RlbCBzcGVjaWZpY2F0aW9uCgorIEluIHRoaXMgU3RhcnRlciBDb2RlLCB3ZSB1c2UgS05OIHRvIGRvIGNsYXNzaWZpY2F0aW9uLiAKCmBgYHtyIGxvYWRsaWJ9CiNzb3VyY2UoIi4uL2xpYi90cmFpbi5SIikgU2luY2Uga25uIGRvZXMgbm90IG5lZWQgdG8gdHJhaW4sIEkgY29tbWVudCB0aGlzIGxpbmUuCnNvdXJjZSgiLi4vbGliL3Rlc3Rfa25uLlIiKQpgYGAKCiMjIyMgTW9kZWwgc2VsZWN0aW9uIHdpdGggY3Jvc3MtdmFsaWRhdGlvbgoqIERvIG1vZGVsIHNlbGVjdGlvbiBieSBjaG9vc2luZyBhbW9uZyBkaWZmZXJlbnQgdmFsdWVzIG9mIHRyYWluaW5nIG1vZGVsIHBhcmFtZXRlcnMuCmBgYHtyIHJ1bmN2LCBldmFsPUZ9CnNvdXJjZSgiLi4vbGliL2Nyb3NzX3ZhbGlkYXRpb25fa25uLlIiKQppZihydW4uY3YpewogIGVycl9jdiA8LSBtYXRyaXgoMCwgbnJvdyA9IGxlbmd0aChrKSwgbmNvbCA9IDIpCiAgZm9yKGkgaW4gMTpsZW5ndGgoaykpewogICAgY2F0KCJrPSIsIGtbaV0sICJcbiIpCiAgICBlcnJfY3ZbaSxdIDwtIGN2LmZ1bmN0aW9uKGRhdF90cmFpbiwgSywga1tpXSkKICBzYXZlKGVycl9jdiwgZmlsZT0iLi4vb3V0cHV0L2Vycl9jdi5SRGF0YSIpCiAgfQp9CmBgYAoKVmlzdWFsaXplIGNyb3NzLXZhbGlkYXRpb24gcmVzdWx0cy4gCmBgYHtyIGN2X3Zpc30KaWYocnVuLmN2KXsKICBsb2FkKCIuLi9vdXRwdXQvZXJyX2N2LlJEYXRhIikKICBlcnJfY3YgPC0gYXMuZGF0YS5mcmFtZShlcnJfY3YpIAogIGNvbG5hbWVzKGVycl9jdikgPC0gYygibWVhbl9lcnJvciIsICJzZF9lcnJvciIpCiAgZXJyX2N2JGsgPSBhcy5mYWN0b3IoaykKICBlcnJfY3YgJT4lIAogICAgZ2dwbG90KGFlcyh4ID0gaywgeSA9IG1lYW5fZXJyb3IsCiAgICAgICAgICAgICAgIHltaW4gPSBtZWFuX2Vycm9yIC0gc2RfZXJyb3IsIHltYXggPSBtZWFuX2Vycm9yICsgc2RfZXJyb3IpKSArIAogICAgZ2VvbV9jcm9zc2JhcigpICsKICAgIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIGhqdXN0ID0gMSkpCn0KCmBgYAoKCiogQ2hvb3NlIHRoZSAiYmVzdCIgcGFyYW1ldGVyIHZhbHVlCmBgYHtyIGJlc3RfbW9kZWx9CmlmKHJ1bi5jdil7CiAgbW9kZWxfYmVzdCA8LSBrW3doaWNoLm1pbihlcnJfY3ZbLDFdKV0KfQpwYXJfYmVzdCA8LSBsaXN0KGsgPSBtb2RlbF9iZXN0KQpgYGAKCiogVHJhaW4gdGhlIG1vZGVsIHdpdGggdGhlIGVudGlyZSB0cmFpbmluZyBzZXQgdXNpbmcgdGhlIHNlbGVjdGVkIG1vZGVsIChtb2RlbCBwYXJhbWV0ZXIpIHZpYSBjcm9zcy12YWxpZGF0aW9uLgpgYGB7ciBmaW5hbF90cmFpbn0KI3RtX3RyYWluPU5BCiN0bV90cmFpbiA8LSBzeXN0ZW0udGltZShmaXRfdHJhaW4gPC0gdHJhaW4oZGF0X3RyYWluLCBwYXJfYmVzdCkpCiNzYXZlKGZpdF90cmFpbiwgZmlsZT0iLi4vb3V0cHV0L2ZpdF90cmFpbi5SRGF0YSIpCmBgYAoKIyMjIFN0ZXAgNTogUnVuIHRlc3Qgb24gdGVzdCBpbWFnZXMKYGBge3IgdGVzdH0KdG1fdGVzdD1OQQppZihydW4udGVzdCl7CiAgbG9hZChmaWxlPSIuLi9vdXRwdXQvZml0X3RyYWluLlJEYXRhIikKICB0bV90ZXN0IDwtIHN5c3RlbS50aW1lKHByZWQgPC0gdGVzdChtb2RlbF9iZXN0LCBkYXRfdGVzdCkpCn0KYGBgCgoqIGV2YWx1YXRpb24KYGBge3J9CmFjY3UgPC0gbWVhbihkYXRfdGVzdCRlbW90aW9uX2lkeCA9PSBwcmVkKQpjYXQoIlRoZSBhY2N1cmFjeSBvZiBtb2RlbDoiLCBtb2RlbF9sYWJlbHNbd2hpY2gubWluKGVycl9jdlssMV0pXSwgImlzIiwgYWNjdSoxMDAsICIlLlxuIikKCmxpYnJhcnkoY2FyZXQpCmNvbmZ1c2lvbk1hdHJpeChwcmVkLCBkYXRfdGVzdCRlbW90aW9uX2lkeCkKYGBgCgpOb3RlIHRoYXQgdGhlIGFjY3VyYWN5IGlzIG5vdCBoaWdoIGJ1dCBpcyBiZXR0ZXIgdGhhbiB0aGF0IG9mIHJhbWRvbSBndWVzcyg0LjUlKS4gCgojIyMgU3VtbWFyaXplIFJ1bm5pbmcgVGltZQpQcmVkaWN0aW9uIHBlcmZvcm1hbmNlIG1hdHRlcnMsIHNvIGRvZXMgdGhlIHJ1bm5pbmcgdGltZXMgZm9yIGNvbnN0cnVjdGluZyBmZWF0dXJlcyBhbmQgZm9yIHRyYWluaW5nIHRoZSBtb2RlbCwgZXNwZWNpYWxseSB3aGVuIHRoZSBjb21wdXRhdGlvbiByZXNvdXJjZSBpcyBsaW1pdGVkLiAKYGBge3IgcnVubmluZ190aW1lfQpjYXQoIlRpbWUgZm9yIGNvbnN0cnVjdGluZyB0cmFpbmluZyBmZWF0dXJlcz0iLCB0bV9mZWF0dXJlX3RyYWluWzFdLCAicyBcbiIpCmNhdCgiVGltZSBmb3IgY29uc3RydWN0aW5nIHRlc3RpbmcgZmVhdHVyZXM9IiwgdG1fZmVhdHVyZV90ZXN0WzFdLCAicyBcbiIpCiNjYXQoIlRpbWUgZm9yIHRyYWluaW5nIG1vZGVsPSIsIHRtX3RyYWluWzFdLCAicyBcbiIpCmNhdCgiVGltZSBmb3IgdGVzdGluZyBtb2RlbD0iLCB0bV90ZXN0WzFdLCAicyBcbiIpCmBgYAoKIyMjUmVmZXJlbmNlCi0gRHUsIFMuLCBUYW8sIFkuLCAmIE1hcnRpbmV6LCBBLiBNLiAoMjAxNCkuIENvbXBvdW5kIGZhY2lhbCBleHByZXNzaW9ucyBvZiBlbW90aW9uLiBQcm9jZWVkaW5ncyBvZiB0aGUgTmF0aW9uYWwgQWNhZGVteSBvZiBTY2llbmNlcywgMTExKDE1KSwgRTE0NTQtRTE0NjIu